/*
 * =====================================================================================
 *
 *       Filename:  2B.cpp
 *
 *    Description:  编程珠玑 第二章 问题B
 *
 *        Version:  1.0
 *        Created:  2011-11-14 9:51:56
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */
#include <iostream>
#include <fstream>
#include <iterator>
#include <ctime>

///////////////////////////////////////////////////////////////////////////////
int _gcd(int m, int n)
{
    if (m < n) {
        return _gcd(n, m);
    } else if (n == 0) {
        return m;
    } else {
        return _gcd(m - n, n);
    }
}

//判断偶数
bool isEven(int m) {
    return (m&0x00000001)!=0x00000001;
}

//分治算法，O(lgn)，利用移位操作代替取模运算
int gcd3(int m, int n) {
    if (m < n) {
        return gcd3(n, m);
    }
    if (n == 0){
        return m;
    } else {
        if (isEven(m)) {
            if (isEven(n)) {
                //m,n都是偶数
                return (gcd3(m>>1, n>>1)<<1);
            } else {
                //m是偶数，n是奇数
                return gcd3(m>>1, n);
            }
        } else {
            if (isEven(n)) {
                //m是奇数，n是偶数
                return gcd3(m, n>>1);
            } else {
                //m,n都是奇数
                return gcd3(n, m-n);
            }
        }
    }
}

//解法一，杂技法
template <class T>
void rotate_array_acrobatics(T *A, int l, int r, int k)
{
    for (int rdis = 0; rdis < gcd3(r - l + 1, k); ++rdis) {
        int j = l + rdis;
        T t = A[j];

        for (int i = j + k; ; i += k) {
            if (i >= r - l + 1) {
                i -= r - l + 1;
            }

            if (i == l) {
                break;
            }

            A[j] = A[i];
            j = i;
        }

        A[j] = t;
    }
}
///////////////////////////////////////////////////////////////////////////////

/*
///////////////////////////////////////////////////////////////////////////////
//解法二，分治法
template <class T>
void rotate_array_devide(T *A, int l, int r, int k)
{
    if (l == r) {
        return;
    }

    if (l + 1 == r) {
        std::swap(A[l], A[r]);
        return;
    }

    int n = r - l + 1;

    if (l < r) {
        int n2 = r - k + 1;

        int cnt = k > n2 ? n2 : k;
        int l1 = l, r1 = l + k;
        int l2 = r - (n - cnt), r2 = r;
        k = k > n2 ? k - n2 : n2 - k;

        for (int i = l1, j = r2; i < r1 && j > l2; ++i, --j) {
            std::swap(A[i], A[j]);
        }
        rotate_array_devide(A, l+cnt, r, k);
    }
}
*/

///////////////////////////////////////////////////////////////////////////////
//解法三，旋转
template <class T>
void rotate_array(T *A, int l, int r)
{
    for (int i = l, j = r; i < j; ++i, --j) {
        std::swap(A[i], A[j]);
    }
}

//将一个具有n个元素的向量左旋转k个位置
template <class T>
void rotate_array_k(T *A, int n, int k)
{
    rotate_array(A, 0, k - 1);
    rotate_array(A, k, n - 1);
    rotate_array(A, 0, n - 1);
}
///////////////////////////////////////////////////////////////////////////////

int main(int argc, char *argv[])
{
    {
        char A[] = {
            'a', 'b', 'c', 'd', 'e', 'f', 'h', 'i', 'j', 'k', 'l', 'm', 'n'
        };

        std::copy(A, A + sizeof(A) / sizeof(char), std::ostream_iterator<char>(std::cout, " "));
        std::cout << std::endl;
        rotate_array_k(A, sizeof(A) / sizeof(char), 4);
        std::copy(A, A + sizeof(A) / sizeof(char), std::ostream_iterator<char>(std::cout, " "));
        std::cout << std::endl;
    }
    {
        char A[] = {
            'a', 'b', 'c', 'd', 'e', 'f', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'l'
        };
        int size = sizeof(A) / sizeof(char);

        std::copy(A, A + size, std::ostream_iterator<char>(std::cout, " "));
        std::cout << std::endl;
        rotate_array_acrobatics(A, 0, size - 1, 4);
        std::copy(A, A + size, std::ostream_iterator<char>(std::cout, " "));
        std::cout << std::endl;
    }

    {
        int pos = 60000000;
        int cnt = 200000000;
        int *B = new int[cnt];

        for (int i = 0; i < cnt; ++i) {
            B[i] = i;
        }

        clock_t start = clock();
        rotate_array_k(B, cnt, pos);
        std::cout << "the running time of rotate_array_k is " << (clock() - start) / CLOCKS_PER_SEC << std::endl;
//        std::ofstream file("2B-S3.txt");
//
//        for (int i = 0; i < cnt; ++i) {
//            file << B[i] << std::endl;
//        }

        delete [] B;
    }
    {
        int pos = 600000;
        int cnt = 2000000;
        int *B = new int[cnt];

        for (int i = 0; i < cnt; ++i) {
            B[i] = i;
        }

        clock_t start = clock();
        rotate_array_acrobatics(B, 0, cnt - 1, pos);
        std::cout << "the running time of rotate_array_acrobatics is " << (clock() - start) / CLOCKS_PER_SEC << std::endl;
//        std::ofstream file("2B-S2.txt");
//
//        for (int i = 0; i < cnt; ++i) {
//            file << B[i] << std::endl;
//        }

        delete [] B;
    }


    return 0;
}
